Leetcode 337.打家劫舍 III

题目描述：

在上次打劫完一条街道之后和一圈房屋后，小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为“根”。 除了“根”之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果两个直接相连的房子在同一天晚上被打劫，房屋将自动报警。

计算在不触动警报的情况下，小偷一晚能够盗取的最高金额。

示例 1:

1
2
3
4
5
6
7
8
9
10

输入: [3,2,3,null,3,null,1]

     3
    / \
   2   3
    \   \ 
     3   1

输出: 7 
解释: 小偷一晚能够盗取的最高金额 = 3 + 3 + 1 = 7.

示例 2:

1
2
3
4
5
6
7
8
9
10

输入: [3,4,5,1,3,null,1]

     3
    / \
   4   5
  / \   \ 
 1   3   1

输出: 9
解释: 小偷一晚能够盗取的最高金额 = 4 + 5 = 9.

链接：

https://leetcode-cn.com/problems/house-robber-iii

题目分析

  依然还是采用动态规划的方法，利用 DFS 的方法遍历二叉树，每个房屋依然有偷和不偷两种选择。我们分析每一个结点作为根能够偷的最大金额，这样搜索后往上归并即可得到答案。

• 偷。那么这个结点的两个子结点都不能偷。
• 不偷。那么这个结点的两个子结点可偷可不偷。

  通过以上的分析我们可以发现，每个结点的选择都可能影响到父节点，因此我们动态规划记录状态的时候需要记录两种选择结果，那么我们可以使用一个结构体进行存储和返回。偷记录为 robber，不偷记录为 norobber。那么我们有这样的状态转移：$\small root.robber=left.norobber+right.norobber+root.val$，而 $\small root.norobber=max(left.robber,left.norobber)+max(right.robber,right.norobber)$。
  从根结点进行 DFS 即可得到答案。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

struct money {
    int robber;
    int norobber;
};

class Solution {
public:
    money dfs(TreeNode* p){
        if(p == nullptr){
            return {0, 0};
        }
        auto leftchild = dfs(p->left);
        auto rightchild = dfs(p->right);
        int robber = leftchild.norobber + rightchild.norobber + p->val;
        int norobber = max(leftchild.robber, leftchild.norobber) + max(rightchild.robber, rightchild.norobber);
        return {robber, norobber};
    }
    int rob(TreeNode* root) {
        auto result = dfs(root);
        return max(result.robber, result.norobber);
    }
};

  时间复杂度：$O(n)$，其中 $n$ 是二叉树的结点数。我们对二叉树进行了一次深度优先搜索遍历。
  空间复杂度：$O(n)$，其中 $n$ 是二叉树的结点数。主要取决于递归栈的深度，当二叉树是一条链时达到最大深度 $n$。